"""
Definition for a point.
"""
class Point:
    def __init__(self, a=0, b=0):
        self.x = a
        self.y = b

# 第一版, 不记录森林中个树的根节点，每次算一下，超时了

class Solution:

    def __init__(self):
        self.points = dict()

    """
    @param n: An integer
    @param m: An integer
    @param operators: an array of point
    @return: an integer array
    """
    def numIslands2(self, n, m, operators):
        result = []
        for point in operators:
            result.append(self.addPoint(n, m, point))
        return result


    def addPoint(self, n, m, point):
        x, y = point.x, point.y
        neighbors = []
        if x != 0     and (x - 1, y) in self.points:
            neighbors.append((x - 1, y))
        if x != n - 1 and (x + 1, y) in self.points:
            neighbors.append((x + 1, y))
        if y != 0     and (x, y - 1) in self.points:
            neighbors.append((x, y - 1))
        if y != m - 1 and (x, y + 1) in self.points:
            neighbors.append((x, y + 1))

        if len(neighbors) == 0:
            self.points[(x, y)] = None
        else:
            treeRoots = set()
            for ne in neighbors:
                curr = ne
                while True:
                    parent = self.points[curr]
                    if parent == None:
                        treeRoots.add(curr)
                        break
                    else:
                        curr = parent
            first = True
            theRoot = None
            for r in treeRoots:
                if first:
                    first = False
                    theRoot = r
                else:
                    self.points[r] = theRoot
            self.points[(x, y)] = theRoot

        for i in range(n):
            str = ""
            for j in range(m):
                if (i, j) in self.points:
                    str += "╋"
                else:
                    str += " "
            print(str)
        print("------------------------------------------------------------------------------")

        return len([i for i in self.points.values() if i == None])

solu = Solution()
print(solu.numIslands2(n = 14, m = 23, operators =[ Point(arr[0], arr[1]) for arr in [
    [3,22],[0,5],[12,14],[13,21],[2,20],[8,10],[4,5],[12,13],[7,13],
    [7,10],[5,13],[8,1],[2,17],[4,17],[9,14],[11,22],[5,2],[5,22],[11,0],
    [7,20],[8,5],[4,13],[6,18],[8,12],[0,0],[9,19],[7,4],[5,12],[9,13],
    [8,11],[11,2],[6,1],[13,6],[0,1],[5,3],[7,17],[11,9],[4,3],[4,8],[6,4],
    [8,17],[8,6],[2,18],[0,15],[9,21],[2,12],[6,0],[1,15],[3,4],[13,2],[0,7],
    [8,0],[10,6],[2,3],[13,7],[1,5],[10,0],[2,19],[12,7],[10,1],[11,13],
    [7,14],[4,6],[3,19],[5,11],[11,18],[3,1],[1,3],[3,9],[7,12],[6,7],[9,12],
    [9,5],[12,3],[10,18],[5,6],[5,21],[3,0],[12,19],[0,3],[4,1],[9,6],[1,12],
    [5,17],[11,6],[0,19],[3,7],[7,1],[13,5],[6,5],[13,20],[8,4],[7,3],[2,2],
    [4,22],[6,21],[4,4],[4,10],[3,17],[12,17],[10,10],[2,22],[6,15],[1,6],[7,6],
    [7,21],[12,8],[8,21],[4,2],[11,1],[10,2],[1,20],[11,3],[8,19],[7,15],[2,5],
    [8,13],[0,20],[7,9],[4,7],[1,4],[5,19],[2,13],[4,11],[10,20]]]))

